package J4_8;

public class test {
    //给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    //
    //子数组
    //是数组中的一个连续部分。
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] dp = new int[n + 1];
        dp[0] = -0x3f3f3f3f;
        for (int i = 1; i <= n ; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i-1],nums[i-1]);
        }
        int max = Integer.MIN_VALUE;
        for (int i : dp) {
            max = Math.max(max, i);
        }
        return max;
    }

    //给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
    //
    //环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是
    // nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
    //
    //子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i],
    // nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
    public static int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        if ( n == 1) {
            return nums[0];
        }
        int[] fmax = new int[n + 1];
        int[] fmin = new int[n + 1];

        fmax[0] = -0x3f3f3f3f;
        fmin[0] = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) {
            fmax[i] = Math.max(fmax[i-1] + nums[i-1],nums[i-1]);
            fmin[i] = Math.min(fmin[i-1] + nums[i-1],nums[i-1]);
        }
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE, sum = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, fmax[i]);
            min = Math.min(min, fmin[i]);
            sum += nums[i-1];
        }
        if (sum == min) return max;
        return Math.max(max, (sum - min));
    }

    //给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
    //子数组
    //（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
    //
    //测试用例的答案是一个 32-位 整数。
    public int maxProduct(int[] nums) {
        int n= nums.length;
        if (n == 1) return nums[0];
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = g[0] = 1;
        int ret = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            int x = nums[i-1], y = f[i-1] * x, z = g[i-1] * x;
            f[i] = Math.max(x, Math.max(y,z));
            g[i] = Math.min(x, Math.min(y,z));
            ret = Math.max(ret, f[i]);
        }

        return ret;

    }

    //给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
    //
    //一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
    //
    //请你返回乘积为正数的最长子数组长度。
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0] > 0 ? 1 : 0;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = g[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (nums[i-1] > 0) {
                f[i] = f[i-1] + 1;
                g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;
            } else if (nums[i-1] < 0) {
                g[i] = f[i-1] + 1;
                f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;
            } else {
                f[i] = g[i] = 0;
            }
        }
        int ret = -1;
        for (int i : f) {
            ret = Math.max(ret, i);
        }
        return ret;
    }


}
